通信ネットワークにおける通信リンクを特徴付ける方法

专利摘要:
本発明は、少なくとも２つの通信ノード（ｎ１,ｎ２,．．．,ｎｐ）を有する通信ネットワークであって、MAC（Media Access Control）レイヤ及びネットワークレイヤを有するネットワークプロトコルを使用して動作する通信ネットワークにおける通信リンクを特徴付けする方法に関する。当該方法は、ドライバを有する通信ノード（ｎ１）からリンクｌ［ｎ１,ｎ２］を通して別の通信ノード（ｎ２）にユニキャストパケットを送出するステップ、ドライバのレベルで、ノード（ｎ１）により、MACレイヤとネットワークレイのレベルで送信特性に関する情報を収集するステップ、収集された情報から、ユニキャストパケットのデリバリレシオ（ｄu）と、ユニキャストパケットを送信する平均時間（PTT）を導出するステップ、ノード（ｎ１）において、mean（PTT）／ｄuを計算することで、MACレイヤとネットワークレイヤのレベルでリンクｌ［ｎ１,ｎ２］の品質を予測するステップを含む。
公开号:JP2011507322A
申请号:JP2010536485
申请日:2008-12-05
公开日:2011-03-03
发明作者:カレラ，マリアンナ；サロニディス，テオドロス；ディオ，クリストフ；ルングレン，ヘンリク
申请人:トムソン ライセンシングＴｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ；
IPC主号:H04W40-12

专利说明:

[0001] 本発明は、通信ネットワークの分野に関する。
本発明は、より詳細には、通信ネットワークにおける通信リンクを特徴付ける方法に関する。]
背景技術

[0002] ワイヤレスメッシュネットワークは、無線リンクにより相互接続されたスタティックノードから構成されるネットワークとして定義される。それぞれのノードは、２つの機能を有し、一方で、レガシーアクセスポイントとしての役割を果たし、クライアントがインターネットに接続するのを可能にし、他方で、ルータとしての役割を果たし、他のノードに代わってパケットを送出する。メッシュノードは、多数の無線インタフェースを有する。典型的に、あるインタフェースは、アクセスポイントの機能に専用にされ、他のインタフェースは、メッシュの接続性に専用にされる。ゲートウェイと呼ばれる幾つかの特別のノードのみがインターネットに接続される。]
[0003] ワイヤレスメッシュネットワークは、公的に共有されるインターネットアクセスのため、街におけるのと同様に、リサーチテストベッドとして大学及び企業の両者で配置されている。
本発明のフレームにおいて、「ネットワークレイヤ」はネットワーキングのＯＳＩモデルにおける（７のうちの）レイヤ３である。]
[0004] Roofnet（J.Bicket, D.Aguayo, S.Biswas and R.Morris. “Architecture and evaluation of an unplanned 802.11b mesh network”− In Mobicom ’05: Processings of the 11th annual international conference on Mobile computing and networking, pages 31-42, New York, NY, USA, 2005.ACMPress − Roofnet website at URL: http://pdos.csail.mit.edu/roofnet/doku.php）、Rice University’s TFA（TFA and Rice wireless network website at URL: http://tfa.rice.edu/）及びUCSB Meshnet（H.Lundgren, K.Ramachandran, E.Belding-Royer, K.Almeroth, M.Benny, A.Hewatt, A.Touma and A.Jardosh. “Experiences from building and using the UCSB meshnet testbed” − InIEEE Wireless Network, April 2006）のようなメッシュネットワークの配置は、研究の目的に主に使用されている。しかし、先に引用されたRoofnet及びTFAネットワークもまた、それらが配置される周辺における専用のコミュニティにより使用される。今日、Tropos及びPacket Hopのような幾つかの企業は、主に公的に共有されるインターネットアクセス向けに、市規模の配置用のメッシュのソリューションを提供する。NetEqualityのようなある非営利団体は、低所得社会をターゲットとしたメッシュに基づくインターネットアクセスを提供している。NetEqualityは、Meraki Networks社からの在庫製品を使用し、この在庫製品は、民間の自主的なメッシュネットワークを配置するためにホームオーナにより使用することもできる。]
発明が解決しようとする課題

[0005] メッシュネットワークにおける１つの課題は、レガシーの有線のインターネットとは非常に異なる環境において、インターネットのようなトラフィック（たとえばTCP，UDP，音声，ストリーミング）を搬送することである。無線リンクの信頼性の欠如及びMACレイヤにより導入される遅延は、パフォーマンスにおける低下としてトランスポート及びアプリケーションレイヤに反映される。これらの問題は、データトラフィックは多数のワイヤレスホップを通して典型的に伝播するメッシュネットワークにおいて更に顕著である。モバイルアドホックネットワーク向けにオリジナルで設計されたルーティングプロトコルは、DSR（D.Johnson, Y.-C.Hu and D.Maltz. “The Dynamic source routing protocol (DSR) for mobile ad hoc networks for IPv4” − February 2007.IETF Internet RFC 4728）、AODV（C.Perkins, E.Belding-Royer, and S.Das −"Ad hoc on-demand distance vector (AODV) routing" − July 2003. IETF Internet RFC 3561）、OLSR（T.Clausen and P.Jacquet − "Optimized link state routing protocol (OLSR)" October 2003. IETF Internet RFC 3626）のようなメッシュネットワークについて適合され、LQSR（R.Draves, J.Padhye, and B.Zill − “Routing in multi-radio, multi-hop wireless mesh networks” In MobiCom ’04: Processing of the 10th annual international conference on Mobile computing and networking, pages 114-128, New York, NY, USA, 2004.ACMPress）及び（Roofnetとして先に識別される）SRCRのような最近に適合されたDSRのバージョンのようなメッシュネットワークについて適合される。AODV及びOLSRアルゴリズムは、IEEE802.11sの進行している標準化の試みで提案されるアルゴリズムにおいて基礎を形成している。係るルーティングプロトコルの目標は、あるコストメトリックを用いてハイパフォーマンスのパスを選択して維持することである。有線ネットワークと対照的に、古典的なホップカウントに基づくルーティングは、マルチホップワイヤレスネットワークにおいて良好に実行しない（たとえば、D.Aguayo, J.Bicket, S.Biswas, G.Judd, and R.Morris − “Link-level measurements from an 802.11b mesh network” − SIGCOMM Comput. Commun. Rev., 34(4):121-132, 2004を参照されたい）。短いパスは、長いパス上の他のリンクよりも低いビットレート及び／又は高いパケット損失を有するリンクからなる場合があり、短いパスに関して低いスループットにつながる。不安定なマルチホップルータを得るため、無線リンク上のトラフィックの負荷に敏感になるため、ETX（D.Couto, D.Aguayo, J.Bicket and R.Morris − “A high-throughput path metric for multi-hop wireless routing” − 2003）及びETT（R.Draves, J.Padhye and B.Zill − “Routing in multi-radio, multi-hop wireless mesh networks” − In Mobicom ’04: Proceedings of the 10th annual international conference on Mobile computing and networking, pages 114-128, New York, NY, USA, 2004 − ACM Press）のような最近提案されたリンクメトリクスが示されている（S.M.Das, H.Pucha, D.Papagianakki, and Y.C.Hu. “Understanding wireless routing link metric dynamics” − InIMC ’07, 2007）。]
[0006] ワイヤレスメッシュネットワークの分野における現在重要な課題は、ルーティングプロトコルがハイパフォーマンスのパスを構築するのを助ける入力として供給される無線リンクの特性を正確に反映するリンクコストのメトリックをどのように設計して実現するかである。]
[0007] たとえば上述されたDSR、AODV及びOLSRプロトコルのようなIETFで標準化されたマルチホップワイヤレスネットワークのルーティングプロトコルは、有線ネットワークで使用される従来のホップカウントメトリック以外のコストをそもそも考慮していない。しかし、ホップカウントは、マルチホップワイヤレスメッシュネットワークについて良好に実行しないことが示されている（たとえば、D.Aguayo等からの先に識別された科学出版物を参照されたい）。いわゆる「ホップカウントメトリック」は、「ロングホップリンク」を選択して、あるルートのホップカウントを最小にする。それぞれ更なるホップについてパフォーマンスが著しく低下するのでホップ数の最小化が良好である一方で、このアプローチは、非生産的であることが分かる。その理由は、これらロングホップリンクが代替的な（ショートホップ）リンクよりも低いビットレートと高いパケットロスを有し、したがってホップカウントのみに基づいてルートの全体的に低いパフォーマンスとなるためである。幾つかの従来の研究は、弱いリンクを排除するため、信号強度の情報の形式でホップカウントをリンク品質の予測で補間することを提案している。係るアプローチは、幾つかのケースにおいてパフォーマンスの改善につながる一方で（H.Lundgren, E.Nordstorm and C.Tschudin − "Copingwith communication gray zones inIEEE 802.11b based ad hoc networks" − In proceedings of the 5thACMInternational Workshop on Wireless Mobile Multimedia (WoWMoM) − September 2002を参照されたい）、信号強度が使用されるビットレートに対して強い相関を有さない場合があることを考慮しておらず（D.Aguayo等からの先に識別された科学出版物を参照されたい）、したがってリンクのパフォーマンスを正確に反映しない。他の従来の研究は、期待される送信の数及び期待されるデータパケットの送信時間に主に基づいて、リンクコストメトリクスを提案している。たとえば、先に引用された“ETX”リンクメトリクスは、ブロードキャストプローブを使用して、あるリンクのパケットロスを予測する。先に引用された“ETT”リンクメトリックは、ETXの上に構築され、現在の帯域幅のパケットペアのプローブに基づいて送信時間の成分を付加する。これら２つのリンクコストメトリクスは、たとえばETX，ETT，EDR及びMICにおけるようなフルマルチホップパスを評価するのを狙いとするルーティングメトリクスにおけるコンポーネントとして使用されている（Y.Yang, J.Wang and R.Kravets − “Interference-aware load balancing for multihop wireless networks” − Technical report, University of Illinois at Urbana-Champain, 2005）。これらのルーティングメトリクスは良好なパスを構築するという目的に対処するが、これらのメトリクスの基礎は、予測された個々のリンクコストである。したがって、リンクコストの良好な推定は、良好なルーティングメトリックの基本となる。]
[0008] ETX及びETTのリンクメトリクスはリンク特性に関する情報を供給するが、それらの既存のアプローチには幾つかの短所がある。ネットワークレベルのブロードキャストパケットプローブ及びユニキャストパケットペアプローブを使用した提案される測定技法は、期待される送信カウント及び全体の帯域幅のそれぞれの量の粗い予測値のみを提供する（先に識別されたR.Draves等及びS.M.Das等の科学出版物を参照されたい）。これら提案され且つ広く使用されている測定技法が与えられると、“ETX”及び“ETT”と呼ばれる技法のうちの１つへの拡張は、同じ関連する不正確さに苦しむ。また、従来技術は、以下の科学出版物を含む。K.-H.Kim及びK.G.Shin − “On accurate measurement of link quality in multihop wireless mesh networks” − In mobiCom ’06: Proceedings of the 12th annual international conference on mobile computing and networking, pages 38-49, New York, NY, USA, 2006 −ACMPress。]
[0009] このK.-H.Kim等からの出版物は、ブロードキャストプローブをMAC（Media Access Control）MIB（Management Information Base）からのユニキャスト送信のカウント統計量で置き換えることで、“ETX”の不正確さに対処する。本発明の発明者の知りうる限り、リンクメトリックの測定された量の改善された精度と共に、リンクメトリックにおける詳細なMAC態様を含むこれまでの研究がない。]
[0010] 以下、主要な従来技術が更に詳細に説明される。
［Expected Transmission Countメトリック］
いわゆる“ETX”（Estimated Transmission Count）の従来技術の技法は、レイヤ３のパケットを上手く伝送するために必要とされる期待される再送信の数としてあるリンクのコストを定義し、高いスループットのパスを選択するため、追加のパスメトリックを構築する。期待される再送信の数を推定するため、あるリンクｄfの順方向及び同じリンクｄrの逆方向でブロードキャストパケットの伝達率（デリバリレシオ）を測定し、次いで、以下を計算する。
ETX＝１／ｄf・ｄr
しかし、ブロードキャストパケットはレートアダプテーションアルゴリズムを受けず、且つ破壊に対してより耐性を示す最も低いビットレートで常に送出されるので、ブロードキャストパケットの伝達率は、高いビットレートで送出されるフレームの伝達率の過大評価となる可能性がある。さらに、ブロードキャストパケットは認められないので、あるリンクの伝達率は、リンクの２つの方向で測定される伝達率の積として計算される。それらのそれぞれは、それぞれの近隣のノードにより送出される受信されたブロードキャストプローブの数をカウントして、（それぞれの送出者について）この数を（送出レートで知られる）期待されるプローブの数で割ることで、リンクの一方の側で測定される。したがって、ETXは、同じブロードキャストの伝達率を使用して、あるリンクの順方向の伝達率を計算し、リンクの他の方向に関して逆方向（ACK）の伝達率を計算する。ACKパケットはデータパケットよりも非常に小さいので、プローブパケットのサイズの選択は、２つのパケットタイプの両者ではなく、２つのパケットタイプのうちの１つを最良にモデル化する。]
[0011] ［Expected Transmission Timeメトリック］
いわゆる“ETT”（Expected Transmission Time）の従来技術の技法は、無線リンクの帯域幅の変動を考慮するために設計される。ETTの目的は、期待される再送信の数と予測されるリンクの帯域幅とから、期待されるユニキャストパケットの送信時間を予測することである。リンクの帯域幅を予測するため、パケットのペアが周期的に送出され、２つのパケットの受信間の遅延が測定される。次いで、帯域幅は、（典型的に）１０サンプルを通した最小の遅延と第二のパケットのサイズとの間の割合として計算される。ETTは、期待される再送信の数と、プローブパケットのサイズと予測される帯域幅の間の割合との積として定義される。
ETT＝ETX（S/B）
この場合、期待される再送信の数はETXであり、Sはパケットサイズであり、Bはリンク帯域幅である。]
[0012] しかし、このパケットのペアに基づく方法は、第二のパケットが第一のパケットの直後に送出されるという仮定の下で帯域幅を推定し、これにより、測定された遅延は、この第二のパケットの空中伝播時間である。８０２．１１のMAC（Media Access Control）により定義される媒体メカニズムへのアクセスのため、第二のパケットは、第一のパケットの直後に送出されない。最良の場合、ノードの近隣の何れもが送信する意思がなく（競合なし）、パケットが第一の送信で上手く受信されたとき、この遅延は、以下の合計である。（１）SIFS（Short Interframe Space）、（２）ACK-time（ACKを受信する時間）、（３）DIFS（DCF Interframe Space）及び（４）（最小の競合窓に基づく）バックオフ時間。他の条件下で、この時間は増加し、たとえば、競合がある場合、第一のパケットの後、ノードは媒体をリリースし、別のノードは、パケットを送出する。暫くした後、第一のノードは、媒体の制御を再び取得し、第二のパケットを送出する。媒体がフリーになるのを待つのに費やした時間は、先に列挙した時間と共に計算された遅延の一部である。第二のパケットが最初の試みで伝達されるのが失敗した場合、第二のパケットは再送信され、先に記載された時間のそれぞれは、それぞれの再送信に１回だけ遅延の一部となる。以下の刊行物で開示されるパケットペアの技法の評価において、著者は、１００秒の窓を通したリンクのビットレートの近似においてこの技法の精度を測定している。"Comparison of routing metrics for static multi-hop wireless networks"（R.Draves, J.Padhye and B.Zill − SIGCOMM Comput. Commun. Rev., 34(4): 133-144, 2004）。（既に上述された）"Routing in multi-radio, multi-hop wireless mesh networks"と題された別の刊行物では、同じ著者は、１０秒を通した最小の帯域幅の予測を考慮している。両方の場合において、予測は、８０２．１１により使用される離散的なビットレートを区別するために十分に正確である。しかし、あるリンクの伝達率を改善するため、レートアダプテーションアルゴリズムは、ほとんど送信毎にレートを適合することができる（たとえば、"MadWifi"ネットワークカードドライバの実現では、最大で４つの異なるレートを１つのレイヤ３のパケットの再送信のために使用することができる）。この場合、最後の１０秒のプローブに基づいた毎秒のリンク帯域幅のサンプルは、それら１０秒で使用されるビットレートを代表せず、平均ビットレート又は最も使用されるビットレートのような良好な予測を推定することはできない。]
課題を解決するための手段

[0013] 本発明は、従来技術の解決策に存在する上述された課題を解決することを目的とする。]
[0014] 従来技術の上述された方法とは対照的に、本発明に係る方法は、（X-UTT）は、ユニキャストパケットでリンクを頻繁にサンプリングし、それぞれのプローブについて、それぞれの再送信のために使用されるビットレートを考慮する。これにより、実際に使用されるビットレートに基づいて、あるフレームの送信において費やされる時間を計算することができる。ショートタイムスケール及びロングタイムスケールに関するETX及びETTの変動の研究は、以下の科学出版物で行われている。"Understanding wireless routing link metric dynamics" − S.M.Das, H.Pucha, D.Papagianakki, and Y.C.Hu − InIMC ’07, 2007。この出版物の著者は、ETX（及びETTのETXコンポーネント）は、非常に短時間のインターバルを通して著しく変動し、バックグランドのトラフィックにより大きく影響されることを示している。この依存性をブロードキャストに基づくプロービングシステムに起因すると考え、著者は、ユニキャストに基づくプロービングシステムの定義の重要性を強調しており、プローブの再送信により導入される大きなオーバヘッドとバランスをとるためにプロービング周波数を低くすることを指摘している。ユニキャストプロービングは、より高い精度を得ることができるが、オーバヘッドがノード数と共に二次的に成長し、且つそれぞれのノードがその近傍のそれぞれのパケットを送出するので、慎重に設計されるべきである。ユニキャストプローブパケットは潜在的に再送信されるので、オーバヘッドは、MACフレームの送信の観点で更に大きい。]
[0015] ユニキャストプローブに基づく前のシステムは、以下に記載されるEARである。"On accurate measurement of link quality in multihop wireless mesh networks" K.-H. Kim and K.G.Shin − In MobiCom ’06: Proceedings of the 12th annual international conference on Mobile computing and networking pages 38-49, New York, NY, USA, 2006 −ACMPress。この出版物に開示されるシステムは、再送信の数及び使用されるビットレートに関する統計的な情報を得るため、MACMIBとインタフェースをとる。これらの統計量は、多数のパケット送信のために１つの値のみを与える。さらに、再送信の数のみがそれらのリンクコストメトリックにおいて考慮される。対照的に、本発明は、それぞれのプローブパケットについて詳細なMACレイヤの情報を構築し、この情報を利用するメトリックを定義する。]
[0016] 本発明は、通信ネットワークにおける通信リンクを特徴付ける方法に関する。]
[0017] 本発明の発明者は、ユニキャストデリバリレシオに対するユニキャストパケットの平均パケット送信時間に関連するリンクコストメトリックとしてX-UTT（cross-layer Unicast Transmission Time）を定義している。このリンクコストメトリックは、X-UTTとして設計され、MAC（Media Access Control）レイヤのエラーコントロールメカニズムの２つの鍵となる態様を捕捉する。このエラーコントロールメカニズムの１つの機能は、失敗したフレームを再送信することで、上位レイヤに対してフレームロスを隠すことである。このように、MACレイヤは、レイヤ３のデリバリレシオを増加し、したがって知覚されるキャパシティを増加する。しかし、あるフレームを再送出することは、パケット送信時間を増加し、知覚されるリンクキャパシティを減少する。X-UTTとして示されるリンクコストメトリックは、上述された態様の両者を捕捉する。]
[0018] 本発明の発明者は、X-UTTとして示されるリンクコストメトリックを計算するために必要とされる量を正確に捕捉するため、測定の手順を設計している。本発明の発明者により設計される測定の手順は、クロスレイヤモニタリングシステムと共に、ユニキャストプローブを使用したプロービングシステムに基づいている。この手順により、本発明者は、X-UTTとして示される上述されたリンクコストメトリックのコンポーネント、すなわちMAC再送信カウント、それぞれのMAC送信のために使用されるビットレート、及びそれぞれの送信当たりのMACバックオフ時間の合計を捕捉することができる。]
[0019] X-UTTとして示されるリンクコストメトリック及び測定の手順のアプローチの新規性の少なくとも幾つかは、ブロードキャストに基づいたプロービングシステムよりも正確であるユニキャストネットワークレイヤパケットの使用、及び、レイヤ２で測定され且つドライバから直接に収集される量からのメトリックの定義である。]
[0020] トラフィックに依存しないメトリックとトラフィックに依存するメトリックといった２つのタイプのルーティングメトリクス間の違いに作用することができる。]
[0021] トラフィックの独立性は、ルーティングアルゴリズムにトラフィックから独立なリンク条件の測度を与えるため、ルーティングメトリクスの一部として使用されるリンクメトリクスにとって一番重要となる。トラフィックに依存するルーティングメトリクスは、ルーティングの不安程度に対処するために必要であり、リンクコストがリンクのトラフィックにより主に決定されるとき、これはルートの切り替えをトリガし、このルート切り替えは、トラフィックにおけるシフトを引き起こし、したがってリンクコストにおける変化を引き起こし、これにより再帰的なルートの切り替えを潜在的にトリガする。]
[0022] 本発明に係る方法は、トラフィックに独立なメトリクス及びトラフィックに依存するメトリクスといった両方のタイプのルーティングメトリクスをサポートする機能を有する。]
[0023] 本発明の主要な貢献は、従来技術と比較して、次の３つのパラグラフにおいて要約される。]
[0024] ある意味では、本発明は、無線通信ネットワークにおけるリンク品質の柔軟且つ正確な特徴付けの方法を提供する。係る方法は、（ｉ）ＯＳＩプロトコルスタックのレイヤ２及びレイヤ３の量から構成されるクロスレイヤリンクメトリック（X-UTTと呼ばれる）、及び（ｉｉ）MACレイヤによるこれらのパケットの送信の詳細な情報を使用してメトリックの量を正確に測定及び計算するユニキャストネットワークレイヤのパケットに基づいてクロスレイヤ測定方法論、から構成される。]
[0025] 本発明は、トラフィックに独立なメトリクス及びトラフィックに依存しないメトリクスの両者をサポートする。トラフィックに独立なメトリクスの場合について、本発明は、無線リンクのキャパシティへの高い相関とネットワークトラフィックへの低い感度を提供する。トラフィックに依存するメトリクスの場合について、本発明は、ネットワークのパフォーマンスを増加するため、トラフィックの切り替えに適合することができる。]
[0026] 無線リンクの特徴付けの従来技術のメトリクスは、ネットワークレイヤで典型的に測定されるユニキャストプローブのパケットのブロードキャストプローブパケットの概略の統計値に基づく。さらに、それらの定義は、トラフィックに依存又はトラフィックに独立の柔軟性を提供しない。したがって、従来技術のメトリクスは、無線リンクの品質の柔軟且つ正確な特徴付けを可能にしない。]
[0027] 本発明は、その広い意味で、少なくとも２つの通信ノード（ｎ１，ｎ２，．．．，ｎｐ）を有する通信ネットワークであって、MAC（Media Access Control）レイヤとネットワークレイヤとを有するネットワークプロトコルを使用して動作する通信ネットワークにおいて通信リンクを特徴付ける方法として定義される。]
[0028] 当該方法は、ドライバを有する通信ノード（ｎ１）から別のノード（ｎ２）にリンク（ｌ［ｎ１，ｎ２］）を介してユニキャストパケットを送出するステップ、前記ドライバのレベルで前記ノード（ｎ１）により、MACレイヤ及びネットワークレイヤの両者のレベルで送信特性に関する情報（Ｉ）を収集するステップ、前記収集された情報（Ｉ）から、ユニキャストパケットのデリバリレシオ（ｄu）及びユニキャストパケットを送信するために平均時間（PTT）を導出するステップ、前記ノード（ｎ１）で、以下の量mean（PTT）／ｄuを計算することで、MACレイヤとネットワークレイヤの両者のレベルで前記リンクｌ［ｎ１，ｎ２］の品質を予測するステップを含む。]
[0029] 実施の形態によれば、ユニキャストパケットを送信する前記時間は、（１）媒体にアクセスする時間、（２）空中にあるフレームを実際に送出する時間、及び（３）確認応答（ACK）を折り返し送出する時間の合計として計算される。]
[0030] 実施の形態によれば、ユニキャストパケット（PTT）を送出する前記時間は、（１）媒体がフリーになるのを待つのに費やした時間、（２）媒体にアクセスする時間、（３）空中にあるフレームを実際に送出する時間、及び（４）確認応答（ACK）を折り返し送出する時間の合計として計算される。今後、用語「ユニキャストプローブ」又は単に「プローブ」は、測定方法論により考慮されるユニキャストネットワークレイヤのパケットを示す。以下に説明されるように、異なる実施の形態によれば、プローブは、専用のパケットであるか、又は既存のトラフィックの一部である場合がある。]
[0031] 本発明によれば、ユニキャストプローブパケットの前記デリバリレシオ（ｄu）は、リンクｌ［ｎ１，ｎ２］で上手く伝達された（レイヤ３で）ユニキャストパケットの数を分子として有し、（レイヤ３で）送出されたユニキャストプローブの数を分母として有する分数として定義される。]
[0032] 特定の実施の形態によれば、送出されるユニキャストパケットは、専用のプローブである。
有利なことに、タイムスタンプは、前記収集するステップの間に収集される。
好ましくは、MACレイヤ再送信カウントは、前記収集するステップの間に収集される。
特定の実施の形態によれば、MACレイヤの送信のために使用されるビットレートは、前記収集するステップの間に収集される。
実施の形態によれば、送信当たりのMACバックオフ時間の合計は、前記収集するステップの間に収集される。]
[0033] 特定の実施の形態によれば、所与のパケットが最終的に上手く伝達されるか否かの事実に関する情報は、前記収集するステップの間の収集される。]
[0034] 本発明は、以下の利点を少なくとも提供する。本発明は、リンクメトリック定義とクロスレイヤの測定方法論のため、高い精度のリンクの特徴付けが得られる。本発明に係る方法は、トラフィックに独立なメトリクスとトラフィックに依存するメトリクスといった両方のタイプのルーティングメトリクスをサポートする機能を有する。トラフィックに対して低い感度が提供される。本発明は、リンクメトリックとリンクキャパシティとの間の良好な相関を得ることができる。]
図面の簡単な説明

[0035] 以下の詳細な説明は、添付図面と共に良好に理解される。
本発明の実施の形態に係る通信ノードの機能ダイアグラムである。
本発明の特定の実施の形態に係る通信ノードの機能ダイアグラムである。
本発明の特定の実施の形態に係る通信ノードの機能ダイアグラムである。
本発明の文脈で使用される通信ノード（装置）の例を示す図である。
本発明に係る方法を例示する図である。]
発明を実施するための最良の形態

[0036] 本発明は、ネットワークのトラフィックに対して低い感度をもつ、無線環境によるリンクの特徴を記述するリンクコストメトリック（link cost metric）を定義する。]
[0037] 図４に示される通信装置Ｄは、通信インタフェース１１、プロセッサ１２、揮発性メモリ１３及び不揮発性メモリ１４を有する。] 図４
[0038] 通信インタフェース１１は、たとえば、ＩＥＥＥ８０２．ｘｙ（たとえば．１１）インタフェースである。]
[0039] プロセッサ１２、揮発性メモリ１３及び不揮発性メモリ１４は、記憶及び処理のために使用される。]
[0040] 図５は、本発明に係る方法を例示する。
図５に示されるように、本発明によれば、少なくとも２つの通信ノード（ｎ１，ｎ２，．．．，ｎｐ）を有する通信ネットワークであって、MAC（Media Access Control）レイヤとネットワークレイヤとを有するネットワークプロトコルを使用して動作する通信ネットワークにおける通信リンクを特徴付ける方法は、以下のステップを含む。] 図５
[0041] ドライバを有する通信ノード（ｎ１）から別のノード（ｎ２）にリンク（ｌ［ｎ１，ｎ２］）を介してユニキャストパケットを送出するステップ。前記ドライバのレベルで前記ノード（ｎ１）により、MACレイヤ及びネットワークレイヤの両者のレベルで送信特性に関する情報（Ｉ）を収集するステップ。前記収集された情報（Ｉ）から、ユニキャストパケットのデリバリレシオ（ｄu）及びユニキャストパケットを送信するための平均時間（PTT）を導出するステップ。前記ノード（ｎ１）で、以下の量mean（PTT）／ｄuを計算することで、MACレイヤとネットワークレイヤの両者のレベルで前記リンクｌ［ｎ１，ｎ２］の品質を予測するステップ。
本方法の異なるステップは、部分的に、同時に行われる可能性がある。]
[0042] 「環境」は、本実施の形態では、信号強度を減衰させること又は全体の信号レベルを増加させることの役割を果たすファクタの集合を示し、限定されるものではないが、ノードの相対的な位置、壁、ドア及び家具のような静的な障害物、移動する人のような一時的な障害物、同じ周波数で送信する他の装置又はマイクロ波オーブンのような関連のないソースのような無線周波の干渉部を含む。]
[0043] この特性は、８０２．１１自身に特化したMACレイヤのメカニズムを捕捉すること、ユニキャストネットワークレイヤのパケットを使用することで達成される。無線環境は、たとえばフレームの破壊による損失を通して、無線リンクの動作に影響を及ぼす可能性がある。MACレイヤで、フレームの損失は、エラーコントロールメカニズム及びレートアダプテーションアルゴリズムといった２つの態様にとって一番重要である。本発明におけるメトリックは、フレーム当たりのレートアダプテーションアルゴリズムを考慮して、知覚されるキャパシティへのMACレイヤのエラーコントロールメカニズムの２つの反対の作用を捕捉する。一方で、失敗したフレームの再送信がレイヤ３のパケットデリバリレシオを増加、従って知覚されるリンクキャパシティを増加し、他方で、フレームを再送信することが時間のかかるものである場合、パケット送信時間は、それぞれのフレーム再送信の送信時間の合計となり、これは、知覚されるリンクキャパシティを増加する。]
[0044] ［メトリックの定義］
X-UTT（cross-layer Unicast Transmission Time）は、レイヤ３のユニキャストパケットのデリバリレシオにより正規化されるレイヤ３のユニキャストパケットを送信する平均時間として定義される。
X-UTT＝mean（PTT）／ｄu3
ここで、PTTは以下に定義されるパケット送信時間であり、ｄu3は、レベル３により見られるユニキャストパケットのデリバリレシオである。]
[0045] また、エレメントｄu3は、本出願におけるｄuとしても示される。したがって、項ｄu3及びｄuは、本出願の文脈で同じ意味を有する。]
[0046] 平均mean(PTT)及びデリバリレシオは、時間窓を通して評価される。デリバリレシオは、（レイヤ３で）送出されたユニキャストプローブの数を通して、リンクで上手く伝達された（レイヤ３での）ユニキャストプローブの数として定義される。全体のパケット送信時間の定義は、MACレイヤメカニズムの記述に従う。それぞれの再送信について、実施の形態によれば、送信時間は、（１）媒体がフリーになるのを待つのに費やされた時間、（２）媒体にアクセスする時間、（３）空中にフレームを実際に送出する時間、及び（４）確認応答（ACK）を折り返し送出する（又は送出しない）時間の合計である。３つのこれらのコンポーネントはリンクで生じたロスに依存する一方、媒体がフリーになるのを待つのに費やされる時間は、ネットワークの競合及びトラフィックの関数である。]
[0047] 別の実施の形態によれば、媒体がフリーになるのを待つのに費やされた時間は、送信時間の計算のために考慮されず、送信時間は、媒体にアクセスするための時間、空中にフレームを実際に送出する時間及びACKを折り返し送出する（又は送出しない）時間の合計である。]
[0048] この実施の形態によれば、X-UTTは環境によるリンク特性を表現するために設計され、トラフィックの負荷に対する感度が低いので、フレーム送信時間FTTは、（１）媒体にアクセスする時間ｔb、（２）空中にフレームを送出する時間ｔt及び（３）ACKを折り返し送出する時間（これは、あるリンクを別のリンクから区別しない一定の量であり、実際に無視することができる）として定義されるが、媒体がフリーになるのを待つのに費やされる時間を考慮しない。
FTT＝ｔb＋ｔt
空中送信時間ｔtは、選択されたビットレートで、レイヤ１のヘッダを送出する時間にMACフレームを送出する時間を加えた時間である。それぞれの再送信について、ｔtの合計であるＴtを以下のように定義する。]
[0049] ここで、ｓｉｚｅはビットでのパケットのサイズであり、Ｒは再送信パターンであり、ｒは使用されたビットレートであり、ｔｘrは、ｒで送出された送信の数である。再送信パターンは、それぞれの再送信のために使用されるビットレートと共に、レイヤ３のユニキャストパケットについて行われた全ての再送信の記述と呼ばれる。４つの数のペアによるこのパターンを、（ｒ0,ｔｘ0）、（ｒ1,ｔｘ1）、（ｒ2,ｔｘ2）、（ｒ3,ｔｘ3）と表現し、これらは、パケットがビットレートｒ0を使用してｔｘ0回再送信され、次いで、ビットレートｒ1を使用してｔｘ1回再送信されたことを意味する。]
[0050] 媒体（ｔb）にアクセスする時間は、DIFSとバックオフ時間の合計として表現され、最も小さいバックオフ時間（IEEE802.11gについて150ミリ秒）がDIFS（IEEE802.11gについて50ミリ秒）よりも著しく大きいため、バックオフ時間のみでこれを近似する。バックオフ時間は固定されたサイズのタイムスロットのランダム数であるので、このランダム変数の期待される値が考慮される。
ｔb＝slotTime*cw/2
cw＝(cwmin +1)*2t − 1
ここでｔは、送出されているプローブについて、前に失敗した送信の数である。]
[0051] それぞれの再送信についてｔbの合計としてＴbが定義される。]
[0052] 全体のパケット送信時間は、ＴtとＴbとの合計である。
PTT＝Ｔt＋Ｔb
［メトリック計算例］
このセクションでは、（最小の競合の窓１５及び最大の競合の窓１０２３、最大の再送信の数８、サンプルレート及びマルチレートのリトライオプションがイネーブルであることを考慮した）MadWifi実現を使用したときのメトリック値の境界の例が与えられ、プローブパケットの送出レートは１プローブ／秒であり、メトリックの計算は、２分の周期を通してX-UTTとして示される。これらの条件下で、X-UTTは、２２７．１９の最小値から７．６６*１０6の最大値（最小の非ゼロのｄuについて）まで変動する。最小値は、最適なケースを考慮して得られ、ここで、X-UTTの予測について考慮される全てのプローブパケットは、最大ビットレート（５４Mbps）を使用して唯一の送信で上手く伝達されている。この場合、X-UTTとして示されるメトリックは、（IEEE802.11gについて７７．５ミリ秒である）最小値Ｔtと（IEEE802.11gの１５０ミリ秒である）最小値Ｔbの合計であるPTTのみに依存する。最大（有限）値は、最悪のケースを考慮して得られ、この場合、全ての考慮されたプローブパケットは、８回再送信されており（これは再送信の最大数である）、唯一のプローブのみが成功である。Ｔtは３３．５ｍｓであり（１Mbpsでの８つの空中送信時間の合計）、Ｔbは８１．８４ｍｓ（８つのバックオフ時間の合計）、ｄu3は１/１２０である。なお、X-UTTはユニキャストデリバリレシオ（ｄu）がゼロであるときに無限値をとる可能性がある。]
[0053] ［測定方法論］
X-UTTにより必要とされる無線リンク状態に関する情報を取得するため、本発明の発明者は、以下のような測定方法論を設計している。ネットワークにおけるそれぞれのノードは、（選択された実施の形態に従って、専用の周期的なパケット及び／又は既存のトラフィックを使用して）ネットワークレイヤのユニキャストパケットをその近隣のそれぞれに送信する。用語「プローブ」は、この測定方法論により考慮されるユニキャストネットワークレイヤのパケットを示す。送信ノードは、次いで、MACレイヤでのモニタリングを実行し、これらのプローブのそれぞれについて以下の情報を収集する。タイムスタンプ、MACレイヤの再送信カウント、それぞれのMACレイヤの再送信のために使用されるビットレート、それぞれの送信当たりのMACバックオフ時間の合計、及びプローブが最終的に上手く伝達されたか否か。さらに、（本発明で定義されたメトリックにより使用されないが）それぞれ上手く伝達されたプローブの受信された信号の強度の指示（RSSI: Received Signal Strength Indication）が収集される。]
[0054] 図１は、本発明の実施の形態に係る、通信ノードの機能ダイアグラムである。
この図に関して、システムの出力は平行四辺形で示される、リンクのコスト予測である。システムのメインブロックは、丸みのあるボックスにより示される、トラフィックジェネレータ、測定値相関器、リンクのコスト予測器である。] 図１
[0055] 「測定値相関器」は、おそらく「MACフレーム送出機能」の一部として、ドライバ内部で実現されることが好ましい。]
[0056] 他の２つのブロック「トラフィックジェネレータ」及び「メトリック予測器」は、ドライバ内部又は外部で実現される。]
[0057] 図１に例示される実施の形態によれば、測定値相関器は、ドライバに統合され、最終的な送信の結果（すなわち、フレームが最終的に受信されたか又は廃棄されたか）、MACレイヤにより行われた再送信の数、及び（それぞれの再送信について１つである）使用されたビットレートのリストのような、あるフレームのMACレイヤの送信に関する詳細を提供する。] 図１
[0058] リンクのコスト予測器は、先の情報を利用するコンピュータプログラムであり、X-UTTとして先に示されたリンクメトリックを計算するためにマッチングステップを実行する。このコンピュータプログラムの位置と、このコンピュータプログラムとドライバとの間の通信がどのように行われるかは、選択された実現に依存する。]
[0059] トラフィックジェネレータは、ユニキャストネットワークレイヤのパケットのソースである。異なる実施の形態によれば、トラフィックジェネレータは、送出されるべき専用のユニキャストパケットをMACレイヤに与えるコンピュータプログラムであるか、又は別の指定されていないトラフィックのソースであるか、或いはハイブリッドのソリューションである。]
[0060] 図２及び図３は、特定の実施の形態に係る、通信ノードの機能ダイアグラムである。
図２に示される例では、最小の変形のみがドライブに提供される。
図３の例では、大部分又は全ての機能がドライバで実現される。勿論、中間的なソリューションが適用される場合がある。] 図２ 図３
[0061] 図２に示される例では、測定値相関器は、ドライバ内部で実現される。
トラフィックジェネレータは、専用のブローブパケットを送出するアプリケーションである。
リンクのコスト予測器は、アプリケーションレイヤのレベルで実現される。] 図２
[0062] 図２では、システムに専用とされるトラフィックジェネレータが記載される（ノードに存在する他のトラフィックはここでは考慮されない）。] 図２
[0063] 「トラフィックジェネレータ」は、パケット、特にプローブパケットを生成するために適合される。この「トラフィックジェネレータ」は、標準的なTCP/IPスタックを使用して又は使用せずに、プローブを送出されるべきMACレイヤに与える。]
[0064] 図２に示される特定の実施の形態によれば、「測定値相関器」は、ドライバで実現されるほんの一部、すなわちカーネルスペースである。この実施の形態では、「リンクコスト予測器」は、アプリケーションとして実現され、このことは、アプリケーションは、測定値相関器によりドライバで収集される情報に直接アクセスすることができないことを意味する。これら２つのブロック間の通信を可能にするため、ソケットを使用することができる。通信は、矢印で示されるように、１方向である。] 図２
[0065] 図３に示される例では、全ての機能ブロックは、ドライバにおいて実現される。
図３で示される例では、測定値相関器、トラフィックジェネレータ及びリンクコスト予測器である全てのシステムブロックは、ドライバで実現される。] 図３
[0066] トラフィックジェネレータは適応的であり、「通常の」ＩＰスタックからトラフィックが現在十分に存在しないリンクでのみ専用のトラフィックを生成する。
ＩＰスタックは、ネットワークレイヤ（レイヤ３）を実現するそれぞれの通信ノードの一部である。]
[0067] この例では、「測定値相関器」は、MACレイヤにより送出されるそれぞれのパケット（又は幾つかのサブサンプル）に関する情報を収集する。「トラフィック／パケットジェネレータ」は、十分なパケットがあるリンクに関して（すなわち、ノードｎからノードｎの近隣のノードのそれぞれに）送出されたか否かを自動的に検出し、そのリンクで専用のパケットを生成する。]
[0068] 図３に示される例では、「リンクコスト予測器」は、ドライバにおいて実現される。ブロック間の通信は、従って明白である。測定値は、何処かに保存されない場合があるが、代わりに最終的なリンクのコストを計算するために即座に使用される。しかし、「リンクコスト」は、この特定の例では、ドライバによりエクスポートされる。] 図３
[0069] ソケットは、前述同様に（しかし今回はメトリック予測器から）使用されるか、又はドライバのＡＰＩを変更することもできる。]
[0070] 先の２つの例は可能な実現であって、限定するものではない。本発明を実現する中間的及び／又は代替的な技術的ソリューションを考慮することもできる。]
[0071] 先の明細書、例及び図面は、本発明に係る方法の改善な説明を提供するものである。本発明の多くの実施の形態は本発明の精神及び範囲から逸脱することなしに行われる場合があるので、本発明は特許請求の範囲に記載される。]

权利要求:

請求項1
少なくとも２つの通信ノードを有する通信ネットワークであって、MAC（MediaAccessControl）レイヤ及びネットワークレイヤを有するネットワークプロトコルを使用して動作する通信ネットワークにおける通信リンクを特徴付けする方法であって、当該方法は、ドライバを有する通信ノード（ｎ１）からリンクｌ［ｎ１,ｎ２］を通して別の通信ノード（ｎ２）にユニキャストパケットを送出するステップと、前記ドライバのレベルで、前記ノード（ｎ１）により、前記MACレイヤとネットワークレイのレベルで送信特性に関する情報を収集するステップと、前記収集された情報から、ユニキャストパケットの伝達率（ｄu）と、ユニキャストパケットを送信する平均時間（PTT）を導出するステップと、前記ノード（ｎ１）において、mean（PTT）／ｄuを計算することで、前記MACレイヤとネットワークレイヤのレベルで前記リンクｌ［ｎ１,ｎ２］の品質を予測するステップと、を含むことを特徴とする方法。
請求項2
前記ユニキャストパケットを送信する時間は、（１）媒体にアクセスする時間、（２）空中にフレームを実際に送出する時間、及び（３）確認応答を折り返し送出する（又は送出しない）時間、の合計として計算される、請求項１記載の通信ネットワークにおける通信リンクを特徴付けする方法。
請求項3
前記ユニキャストパケットを送信する時間は、（１）媒体がフリーになるのを待つのに費やした時間、（２）前記媒体にアクセスする時間、（３）空中にフレームを実際に送出する時間、及び（４）確認応答を折り返し送出する（又は送出しない）時間、の合計として計算される、請求項１記載の通信ネットワークにおける通信リンクを特徴付けする方法。
請求項4
ユニキャストプローブパケットの前記伝達率は、リンクｌ［ｎ１,ｎ２］で上手く伝達された（レイヤ３での）ユニキャストパケットの数を分子として有し、（レイヤ３で）送出されたユニキャストプローブの数を分母として有する分数として定義される、請求項１乃至３の何れか記載の通信ネットワークにおける通信リンクを特徴付けする方法。
請求項5
前記送出されたユニキャストパケットは、専用のプローブである、請求項１乃至４の何れか記載の通信ネットワークにおける通信リンクを特徴付けする方法。
請求項6
前記収集するステップの間にタイムスタンプが収集される、請求項１乃至５の何れか記載の通信ネットワークにおける通信リンクを特徴付けする方法。
請求項7
前記収集するステップの間にMACレイヤの再送信カウントが収集される、請求項１乃至６の何れか記載の通信ネットワークにおける通信リンクを特徴付けする方法。
請求項8
前記収集するステップの間にMACレイヤの送信のために使用されるビットレートが収集される、請求項１乃至７の何れか記載の通信ネットワークにおける通信リンクを特徴付けする方法。
請求項9
前記収集するステップの間に送信毎のMACバックオフ時間の合計が収集される、請求項１乃至８の何れか記載の通信ネットワークにおける通信リンクを特徴付けする方法。
請求項10
前記収集するステップの間に所与のパケットが上手く伝達されたか否かの事実に関する情報が収集される、請求項１乃至９の何れか記載の通信ネットワークにおける通信リンクを特徴付けする方法。